import java.util.*;

/**
 * @author LKQ
 * @date 2022/4/22 15:04
 * @description
 */
public class Solution {
    public static void main(String[] args) {
        Solution solution = new Solution();
        int[][] matrix = {{1}};
        solution.longestIncreasingPath(matrix);
    }

    public int longestIncreasingPath(int[][] matrix) {
        int m = matrix.length, n = matrix[0].length;
        // 超级源点到其他点的路径长度
        List<Pair> list = new ArrayList<>();
        // 根据二维数组转一维完成映射
        Map<Integer, Pair> map = new HashMap<>();
        for (int i = 0; i < m; i++) {
            for (int j = 0; j < n; j++) {
                Pair pair = new Pair(i, j, matrix[i][j]);
                list.add(pair);
                map.put(i * n + j, pair);
            }
        }
        Collections.sort(list, (a, b) -> a.value - b.value);
        int[][] dir = {{-1, 0}, {1, 0}, {0, 1}, {0, -1}};
        int max = 1;
        for (int i = 0; i < m * n; i++) {
            Pair pair = list.get(i);
            int x = pair.x, y = pair.y, value = pair.value, maxLength = pair.maxLength;
            for (int j = 0; j < 4; j++) {
                int nx = x + dir[j][0], ny = y + dir[j][1];
                if (nx >= 0 && nx < m && ny >= 0 && ny < n && matrix[nx][ny] > value) {
                    Pair pair1 = map.get(nx * n + ny);
                    pair1.maxLength = Math.max(pair1.maxLength, maxLength + 1);
                    max = Math.max(max, pair1.maxLength);
                }
            }
        }
        return max;
    }
}

class Pair {
    int x;
    int y;
    int value;
    int maxLength;

    public Pair(int x, int y, int value) {
        this.x = x;
        this.y = y;
        this.value = value;
        this.maxLength = 1;
    }
}
